1398C Good Subarrays
1398C Good Subarrays
题目链接:Good Subarrays
**题目大意:**给定一个字符串,需要找到有多少个区间使得其区间内每个元素的和为区间长度。
题解:
其区间内每个元素的和为区间长度, 也就是 区间和 = 区间长。
区间和可以用前缀和来维护,因此,可以得到:
移向,可以得到:
统计 ,如果出现重复的,那么 ,因此 可以与前面的所有项组合。
特别需要注意的,当 时,那么, 区间和也就等于区间长度,因此 。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
long long sum[1000001], appear[1000001]; //记录前缀和, 记录出现过几次
int main() {
long long t, n, ans = 0;
scanf("%lld", &t);
while (t >= 1) {
t--;
memset(sum, 0, sizeof(sum));
memset(appear, 0, sizeof(appear));
appear[100000] = 1; //注意避免 sum[i] - i 越界!因此,把 100000 作为起点
ans = 0;
scanf("%lld", &n);
char c;
for (long long i = 1; i <= n; i++) {
cin >> c;
sum[i] = sum[i - 1] + c - '0'; //前缀和
ans = ans + appear[sum[i] - i + 100000];
appear[sum[i] - i + 100000]++; //更新答案
}
printf("%lld\n", ans);
}
return 0;
}